/*-------------------------------------------------------------------------
 *
 * freespace.c
 *	  POSTGRES 空闲空间映射，用于快速查找关系中的空闲空间
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/storage/freespace/freespace.c
 *
 *
 * NOTES:
 *
 *	自由空间映射跟踪页面上的空闲空间量，并允许快速搜索具有足够空闲空间的页面。FSM存储在所有堆关系的专用关系分叉中，以及那些需要它的索引访问方法（另见 indexfsm.c）。有关更多信息，请参阅 README。
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/htup_details.h"
#include "access/xloginsert.h"
#include "access/xlogutils.h"
#include "miscadmin.h"
#include "storage/freespace.h"
#include "storage/fsm_internals.h"
#include "storage/lmgr.h"
#include "storage/smgr.h"


/*
 * 我们只使用一个字节来存储页面上的空闲空间量，
 * 因此我们将页面可以拥有的空闲空间量分为 256 个不同类别。
 * 最高类别 255 表示具有至少
 * MaxFSMRequestSize 字节空闲空间的页面，第二高类别
 * 表示从 254 * FSM_CAT_STEP（包含）到
 * MaxFSMRequestSize（不包含）的范围。
 *
 * MaxFSMRequestSize 取决于架构和 BLCKSZ，但假设
 * 默认 8k BLCKSZ，并且 MaxFSMRequestSize 为 8164 字节，
 * 类别如下所示：
 *
 *
 * 范围   类别
 * 0 - 31   0
 * 32 - 63   1
 * ...    ...  ...
 * 8096 - 8127 253
 * 8128 - 8163 254
 * 8164 - 8192 255
 *
 * MaxFSMRequestSize 之所以特殊，是因为如果 MaxFSMRequestSize
 * 不等于一个范围边界，恰好有 MaxFSMRequestSize
 * 字节空闲空间的页面将无法满足对 MaxFSMRequestSize
 * 字节的请求。如果在完全空的页面上没有超过 MaxFSMRequestSize 字节的空闲空间，
 * 那将意味着我们永远无法满足恰好为 MaxFSMRequestSize 字节的请求。
 */
#define FSM_CATEGORIES	256
#define FSM_CAT_STEP	(BLCKSZ / FSM_CATEGORIES)
#define MaxFSMRequestSize	MaxHeapTupleSize

/*
 * 磁盘树的深度。我们需要能够寻址 2^32-1 个块，
 * 而 1626 是满足 X^3 >= 2^32-1 的最小数字。同样，
 * 256 是满足 X^4 >= 2^32-1 的最小数字。实际上，
 * 这意味着 4096 字节是我们能够在 3 级树中使用的最小 BLCKSZ，
 * 512 是我们支持的最小值。
 */
#define FSM_TREE_DEPTH	((SlotsPerFSMPage >= 1626) ? 3 : 4)

#define FSM_ROOT_LEVEL	(FSM_TREE_DEPTH - 1)
#define FSM_BOTTOM_LEVEL 0

/*
 * 内部 FSM 例程基于逻辑寻址方案。
 * 树的每一层可以被视为一个单独可寻址的文件。
 */
typedef struct
{
	int			level;			/* level */
	int			logpageno;		/* 层内的页面编号 */
} FSMAddress;

/* 根页面的地址。 */
static const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0};

/* 导航树的函数 */
static FSMAddress fc_fsm_get_child(FSMAddress fc_parent, uint16 fc_slot);
static FSMAddress fc_fsm_get_parent(FSMAddress fc_child, uint16 *fc_slot);
static FSMAddress fc_fsm_get_location(BlockNumber fc_heapblk, uint16 *fc_slot);
static BlockNumber fc_fsm_get_heap_blk(FSMAddress fc_addr, uint16 fc_slot);
static BlockNumber fc_fsm_logical_to_physical(FSMAddress fc_addr);

static Buffer fc_fsm_readbuf(Relation fc_rel, FSMAddress fc_addr, bool fc_extend);
static void fc_fsm_extend(Relation fc_rel, BlockNumber fc_fsm_nblocks);

/* 将空闲空间量转换为 FSM 类别的函数 */
static uint8 fc_fsm_space_avail_to_cat(Size fc_avail);
static uint8 fc_fsm_space_needed_to_cat(Size fc_needed);
static Size fc_fsm_space_cat_to_avail(uint8 fc_cat);

/* 各种操作的工作函数 */
static int	fc_fsm_set_and_search(Relation fc_rel, FSMAddress fc_addr, uint16 fc_slot,
							   uint8 fc_newValue, uint8 fc_minValue);
static BlockNumber fc_fsm_search(Relation fc_rel, uint8 fc_min_cat);
static uint8 fc_fsm_vacuum_page(Relation fc_rel, FSMAddress fc_addr,
							 BlockNumber fc_start, BlockNumber fc_end,
							 bool *fc_eof);
static bool fc_fsm_does_block_exist(Relation fc_rel, BlockNumber fc_blknumber);


/******** 公共 API ********/


/*
 * GetPageWithFreeSpace - 尝试在给定的关系中找到至少具有指定数量空闲空间的页面。
 *
 * 如果成功，返回块号；如果不成功，返回 InvalidBlockNumber。
 *
 * 调用者必须准备好处理返回的页面可能在调用者获取锁时可用空闲空间不足的情况。
 * 在这种情况下，调用者应报告该页面上实际可用的空闲空间，然后重试（请参阅
 * RecordAndGetPageWithFreeSpace）。如果返回 InvalidBlockNumber，则扩展关系。
 *
 * 如果发现任何 FSM 条目指向关系末尾后的块，这可能会触发 FSM 更新。
 */
BlockNumber GetPageWithFreeSpace(Relation fc_rel, Size fc_spaceNeeded)
{
	uint8		fc_min_cat = fc_fsm_space_needed_to_cat(fc_spaceNeeded);

	return fc_fsm_search(fc_rel, fc_min_cat);
}

/*
 * RecordAndGetPageWithFreeSpace - 更新有关页面的信息并重试。
 *
 * 我们提供这种组合形式以节省一些锁定开销，与单独的 RecordPageWithFreeSpace + GetPageWithFreeSpace 调用相比。
 * 也有一些努力返回接近旧页面的页面；如果在相同的 FSM 页面上有一个空闲空间足够的页面
 * 与旧页面位置相同，则该页面为首选。
 */
BlockNumber RecordAndGetPageWithFreeSpace(Relation fc_rel, BlockNumber fc_oldPage,
							  Size fc_oldSpaceAvail, Size fc_spaceNeeded)
{
	int			fc_old_cat = fc_fsm_space_avail_to_cat(fc_oldSpaceAvail);
	int			fc_search_cat = fc_fsm_space_needed_to_cat(fc_spaceNeeded);
	FSMAddress	fc_addr;
	uint16		fc_slot;
	int			fc_search_slot;

	/* 获取表示堆块的 FSM 字节的位置 */
	fc_addr = fc_fsm_get_location(fc_oldPage, &fc_slot);

	fc_search_slot = fc_fsm_set_and_search(fc_rel, fc_addr, fc_slot, fc_old_cat, fc_search_cat);

	/*
	 * 如果 fsm_set_and_search 找到合适的新块，返回该块。
	 * 否则，照常进行搜索。
	 */
	if (fc_search_slot != -1)
	{
		BlockNumber fc_blknum = fc_fsm_get_heap_blk(fc_addr, fc_search_slot);

		/*
		 * 检查 blknum 是否确实在关系中。在这种情况下，不要尝试
		 * 更新 FSM，只需回退到其他情况。
		 */
		if (fc_fsm_does_block_exist(fc_rel, fc_blknum))
			return fc_blknum;
	}
	return fc_fsm_search(fc_rel, fc_search_cat);
}

/*
 * RecordPageWithFreeSpace - 更新关于页面的信息。
 *
 * 请注意，如果新的 spaceAvail 值高于存储在 FSM 中的旧值，
 * 该空间可能在下一个 FreeSpaceMapVacuum 调用之前不可见，
 * 该调用更新上层页面。
 */
void RecordPageWithFreeSpace(Relation fc_rel, BlockNumber fc_heapBlk, Size fc_spaceAvail)
{
	int			fc_new_cat = fc_fsm_space_avail_to_cat(fc_spaceAvail);
	FSMAddress	fc_addr;
	uint16		fc_slot;

	/* 获取表示堆块的 FSM 字节的位置 */
	fc_addr = fc_fsm_get_location(fc_heapBlk, &fc_slot);

	fc_fsm_set_and_search(fc_rel, fc_addr, fc_slot, fc_new_cat, 0);
}

/*
 * XLogRecordPageWithFreeSpace - 类似于 RecordPageWithFreeSpace，用于
 *		WAL 重放。
 */
void XLogRecordPageWithFreeSpace(RelFileNode fc_rnode, BlockNumber fc_heapBlk,
							Size fc_spaceAvail)
{
	int			fc_new_cat = fc_fsm_space_avail_to_cat(fc_spaceAvail);
	FSMAddress	fc_addr;
	uint16		fc_slot;
	BlockNumber fc_blkno;
	Buffer		fc_buf;
	Page		fc_page;

	/* 获取表示堆块的 FSM 字节的位置 */
	fc_addr = fc_fsm_get_location(fc_heapBlk, &fc_slot);
	fc_blkno = fc_fsm_logical_to_physical(fc_addr);

	/* 如果页面尚不存在，则扩展 */
	fc_buf = XLogReadBufferExtended(fc_rnode, FSM_FORKNUM, fc_blkno, RBM_ZERO_ON_ERROR,
								 InvalidBuffer);
	LockBuffer(fc_buf, BUFFER_LOCK_EXCLUSIVE);

	fc_page = BufferGetPage(fc_buf);
	if (PageIsNew(fc_page))
		PageInit(fc_page, BLCKSZ, 0);

	if (fsm_set_avail(fc_page, fc_slot, fc_new_cat))
		MarkBufferDirtyHint(fc_buf, false);
	UnlockReleaseBuffer(fc_buf);
}

/*
 * GetRecordedFreeSpace - 根据 FSM 返回特定页面上的空闲空间量。
 */
Size GetRecordedFreeSpace(Relation fc_rel, BlockNumber fc_heapBlk)
{
	FSMAddress	fc_addr;
	uint16		fc_slot;
	Buffer		fc_buf;
	uint8		fc_cat;

	/* 获取表示堆块的 FSM 字节的位置 */
	fc_addr = fc_fsm_get_location(fc_heapBlk, &fc_slot);

	fc_buf = fc_fsm_readbuf(fc_rel, fc_addr, false);
	if (!BufferIsValid(fc_buf))
		return 0;
	fc_cat = fsm_get_avail(BufferGetPage(fc_buf), fc_slot);
	ReleaseBuffer(fc_buf);

	return fc_fsm_space_cat_to_avail(fc_cat);
}

/*
 * FreeSpaceMapPrepareTruncateRel - 为截断关系做准备。
 *
 * nblocks 是堆的新大小。
 *
 * 返回新的 FSM 的块数。
 * 如果它是 InvalidBlockNumber，则没有要截断的内容；
 * 否则，调用者负责调用 smgrtruncate()
 * 来截断 FSM 页面，以及 FreeSpaceMapVacuumRange()
 * 来更新 FSM 中的上层页面。
 */
BlockNumber FreeSpaceMapPrepareTruncateRel(Relation fc_rel, BlockNumber fc_nblocks)
{
	BlockNumber fc_new_nfsmblocks;
	FSMAddress	fc_first_removed_address;
	uint16		fc_first_removed_slot;
	Buffer		fc_buf;

	/*
	 * 如果该关系尚未创建 FSM，则没有要截断的内容。
	 */
	if (!smgrexists(RelationGetSmgr(fc_rel), FSM_FORKNUM))
		return InvalidBlockNumber;

	/* 获取 FSM 中第一个删除的堆块的位置 */
	fc_first_removed_address = fc_fsm_get_location(fc_nblocks, &fc_first_removed_slot);

	/*
	 * 将最后一个剩余的 FSM 页面尾部设为零。如果表示第一个
	 * 删除的堆块的槽在页面边界上，即 first_removed_address 指向的
	 * FSM 页面上的第一个槽，我们可以直接截断该页面。
	 */
	if (fc_first_removed_slot > 0)
	{
		fc_buf = fc_fsm_readbuf(fc_rel, fc_first_removed_address, false);
		if (!BufferIsValid(fc_buf))
			return InvalidBlockNumber;	/* 没有要做的事情；FSM 已经
										 * 更小了 */
		LockBuffer(fc_buf, BUFFER_LOCK_EXCLUSIVE);

		/* 从这里到更改记录时不报告错误 */
		START_CRIT_SECTION();

		fsm_truncate_avail(BufferGetPage(fc_buf), fc_first_removed_slot);

		/*
		 * 这个更改是非关键的，因为 fsm_does_block_exist() 会
		 * 阻止我们返回被截断的块。然而，由于这可能删除多达
		 * SlotsPerFSMPage 个槽，因此避免那么多 fsm_does_block_exist()
		 * 的拒绝开销是件好事。使用完整的
		 * MarkBufferDirty()，而不是 MarkBufferDirtyHint()。
		 */
		MarkBufferDirty(fc_buf);

		/*
		 * 类似于 MarkBufferDirtyHint() 进行 WAL 日志记录，
		 * 只是为了避免在这一点上与文件的其余部分不同。这是
		 * 可选的；请参阅 README 中对完整页面图像的提及。
		 * XXX 考虑使用 XLogSaveBufferForHint() 以更接近相似性。
		 *
		 * 高级操作在 WAL 重放时调用我们。如果我们在 XLOG_SMGR_TRUNCATE
		 * 刷新到磁盘之前崩溃，主分支长度未发生变化，且我们的分支保持有效。
		 * 如果我们在该刷新之后崩溃，重做将返回此处。
		 */
		if (!InRecovery && RelationNeedsWAL(fc_rel) && XLogHintBitIsNeeded())
			log_newpage_buffer(fc_buf, false);

		END_CRIT_SECTION();

		UnlockReleaseBuffer(fc_buf);

		fc_new_nfsmblocks = fc_fsm_logical_to_physical(fc_first_removed_address) + 1;
	}
	else
	{
		fc_new_nfsmblocks = fc_fsm_logical_to_physical(fc_first_removed_address);
		if (smgrnblocks(RelationGetSmgr(fc_rel), FSM_FORKNUM) <= fc_new_nfsmblocks)
			return InvalidBlockNumber;	/* 没有要做的事情；FSM 已经
										 * 更小了 */
	}

	return fc_new_nfsmblocks;
}

/*
 * FreeSpaceMapVacuum - 更新关系的 FSM 中的上层页面
 *
 * 我们假设底层页面已经使用新的空闲空间信息进行更新。
 */
void FreeSpaceMapVacuum(Relation fc_rel)
{
	bool		fc_dummy;

	/* 从根开始递归扫描树 */
	(void) fc_fsm_vacuum_page(fc_rel, FSM_ROOT_ADDRESS,
						   (BlockNumber) 0, InvalidBlockNumber,
						   &fc_dummy);
}

/*
 * FreeSpaceMapVacuumRange - 更新关系的 FSM 中的上层页面
 *
 * 如上，但假设仅堆页面在 start 和 end-1 之间（包含）有新的
 * 空闲空间信息，因此仅更新覆盖该块范围的上层槽。
 * end == InvalidBlockNumber 等同于“关系的其余部分”。
 */
void FreeSpaceMapVacuumRange(Relation fc_rel, BlockNumber fc_start, BlockNumber fc_end)
{
	bool		fc_dummy;

	/* 从根开始递归扫描树 */
	if (fc_end > fc_start)
		(void) fc_fsm_vacuum_page(fc_rel, FSM_ROOT_ADDRESS, fc_start, fc_end, &fc_dummy);
}

/******** 内部例程 ********/

/*
 * 返回对应 x 字节的空闲空间类别
 */
static uint8 fc_fsm_space_avail_to_cat(Size fc_avail)
{
	int			fc_cat;

	Assert(fc_avail < BLCKSZ);

	if (fc_avail >= MaxFSMRequestSize)
		return 255;

	fc_cat = fc_avail / FSM_CAT_STEP;

	/*
	 * 最高类别 255 保留用于 MaxFSMRequestSize 字节或更
	 * 多。
	 */
	if (fc_cat > 254)
		fc_cat = 254;

	return (uint8) fc_cat;
}

/*
 * 返回给定类别所表示的空闲空间范围的下限。
 */
static Size fc_fsm_space_cat_to_avail(uint8 fc_cat)
{
	/* 最高类别恰好表示 MaxFSMRequestSize 字节。 */
	if (fc_cat == 255)
		return MaxFSMRequestSize;
	else
		return fc_cat * FSM_CAT_STEP;
}

/*
 * 页面需要属于哪个类别，以容纳 x 字节的数据？
 * 当 fsm_space_avail_to_cat() 向下舍入时，这需要向上舍入。
 */
static uint8 fc_fsm_space_needed_to_cat(Size fc_needed)
{
	int			fc_cat;

	/* 不能请求超过最高类别所表示的空间 */
	if (fc_needed > MaxFSMRequestSize)
		elog(ERROR, "invalid FSM request size %zu", fc_needed);

	if (fc_needed == 0)
		return 1;

	fc_cat = (fc_needed + FSM_CAT_STEP - 1) / FSM_CAT_STEP;

	if (fc_cat > 255)
		fc_cat = 255;

	return (uint8) fc_cat;
}

/*
 * 返回 FSM 页面的物理块编号
 */
static BlockNumber fc_fsm_logical_to_physical(FSMAddress fc_addr)
{
	BlockNumber fc_pages;
	int			fc_leafno;
	int			fc_l;

	/*
	 * 计算给定页面下方第一个叶子页面的逻辑页面编号。
	 */
	fc_leafno = fc_addr.logpageno;
	for (fc_l = 0; fc_l < fc_addr.level; fc_l++)
		fc_leafno *= SlotsPerFSMPage;

	/* 计算访问该叶子页面所需的上层节点 */
	fc_pages = 0;
	for (fc_l = 0; fc_l < FSM_TREE_DEPTH; fc_l++)
	{
		fc_pages += fc_leafno + 1;
		fc_leafno /= SlotsPerFSMPage;
	}

	/*
	 * 如果我们请求的页面不在底部层，则从上面计算的
	 * 额外下层页面中减去。
	 */
	fc_pages -= fc_addr.level;

	/* 将页面计数转换为 0 基块编号 */
	return fc_pages - 1;
}

/*
 * 返回对应于给定堆块的 FSM 位置。
 */
static FSMAddress fc_fsm_get_location(BlockNumber fc_heapblk, uint16 *fc_slot)
{
	FSMAddress	fc_addr;

	fc_addr.level = FSM_BOTTOM_LEVEL;
	fc_addr.logpageno = fc_heapblk / SlotsPerFSMPage;
	*fc_slot = fc_heapblk % SlotsPerFSMPage;

	return fc_addr;
}

/*
 * 返回 FSM 中给定位置对应的堆块编号。
 */
static BlockNumber fc_fsm_get_heap_blk(FSMAddress fc_addr, uint16 fc_slot)
{
	Assert(fc_addr.level == FSM_BOTTOM_LEVEL);
	return ((unsigned int) fc_addr.logpageno) * SlotsPerFSMPage + fc_slot;
}

/*
 * 给定一个子页面的逻辑地址，获取父页面的逻辑页面编号，以及对应于子页面的父页面中的槽位。
 */
static FSMAddress fc_fsm_get_parent(FSMAddress fc_child, uint16 *fc_slot)
{
	FSMAddress	fc_parent;

	Assert(fc_child.level < FSM_ROOT_LEVEL);

	fc_parent.level = fc_child.level + 1;
	fc_parent.logpageno = fc_child.logpageno / SlotsPerFSMPage;
	*fc_slot = fc_child.logpageno % SlotsPerFSMPage;

	return fc_parent;
}

/*
 * 给定父页面的逻辑地址和槽位编号，获取对应的子页面的逻辑地址。
 */
static FSMAddress fc_fsm_get_child(FSMAddress fc_parent, uint16 fc_slot)
{
	FSMAddress	fc_child;

	Assert(fc_parent.level > FSM_BOTTOM_LEVEL);

	fc_child.level = fc_parent.level - 1;
	fc_child.logpageno = fc_parent.logpageno * SlotsPerFSMPage + fc_slot;

	return fc_child;
}

/*
 * 读取FSM页面。
 *
 * 如果页面不存在，则返回InvalidBuffer，或者如果'extend'为真，则扩展FSM文件。
 */
static Buffer fc_fsm_readbuf(Relation fc_rel, FSMAddress fc_addr, bool fc_extend)
{
	BlockNumber fc_blkno = fc_fsm_logical_to_physical(fc_addr);
	Buffer		fc_buf;
	SMgrRelation fc_reln;

	/*
	 * 注意：如果 relcache 条目被关闭，重用此 smgr 指针可能会失败。只要我们在这里和最后一次使用指针之间只执行 smgr 级别的操作，这样做是安全的。
	 */
	fc_reln = RelationGetSmgr(fc_rel);

	/*
	 * 如果我们还没有缓存FSM的大小，先检查一下它。同时再次检查请求的块是否似乎超出了结束，因为我们的缓存值可能过时。（我们在截断时发送smgr无效消息，但在扩展时不发送。）
	 */
	if (fc_reln->smgr_cached_nblocks[FSM_FORKNUM] == InvalidBlockNumber ||
		fc_blkno >= fc_reln->smgr_cached_nblocks[FSM_FORKNUM])
	{
		/* 使缓存失效，以便smgrnblocks请求内核。 */
		fc_reln->smgr_cached_nblocks[FSM_FORKNUM] = InvalidBlockNumber;
		if (smgrexists(fc_reln, FSM_FORKNUM))
			smgrnblocks(fc_reln, FSM_FORKNUM);
		else
			fc_reln->smgr_cached_nblocks[FSM_FORKNUM] = 0;
	}

	/* 处理超出 EOF 的请求 */
	if (fc_blkno >= fc_reln->smgr_cached_nblocks[FSM_FORKNUM])
	{
		if (fc_extend)
			fc_fsm_extend(fc_rel, fc_blkno + 1);
		else
			return InvalidBuffer;
	}

	/*
	 * 使用ZERO_ON_ERROR模式，并在必要时初始化页面。无论如何，FSM信息都不准确，因此清除损坏的页面比返回错误要好。由于FSM更改没有WAL日志记录，因此崩溃时所谓的撕裂页面问题可能导致页面具有损坏的头部，例如。
	 *
	 * 初始化页面的部分比看起来复杂，因为可能有多个后端同时执行此操作，而且我们希望在正常路径中不无谓地获取缓冲区锁定，其中页面是好的。我们必须获取锁以初始化页面，因此在获取锁后重新检查页面的新ness，以防其他人已经执行了此操作。此外，由于我们最初在没有锁的情况下检查PageIsNew，因此可能会跌落并在其他人仍在初始化页面时返回缓冲区（即，我们可能看到pd_upper已设置但其他页面头部字段仍为零）。对于将自己获取缓冲锁的调用方，这没有害处，但有些调用方在没有任何锁的情况下检查页面。后者只有在不依赖于页面头部拥有正确内容的情况下才可以。当前的使用是安全的，因为PageGetContents()不需要那个。
	 */
	fc_buf = ReadBufferExtended(fc_rel, FSM_FORKNUM, fc_blkno, RBM_ZERO_ON_ERROR, NULL);
	if (PageIsNew(BufferGetPage(fc_buf)))
	{
		LockBuffer(fc_buf, BUFFER_LOCK_EXCLUSIVE);
		if (PageIsNew(BufferGetPage(fc_buf)))
			PageInit(BufferGetPage(fc_buf), BLCKSZ, 0);
		LockBuffer(fc_buf, BUFFER_LOCK_UNLOCK);
	}
	return fc_buf;
}

/*
 * 确保FSM分支至少长为fsm_nblocks，如果必要，使用空页面进行扩展。这里的空页面是指填充了零的页面，意味着没有自由空间。
 */
static void fc_fsm_extend(Relation fc_rel, BlockNumber fc_fsm_nblocks)
{
	BlockNumber fc_fsm_nblocks_now;
	PGAlignedBlock fc_pg;
	SMgrRelation fc_reln;

	PageInit((Page) fc_pg.data, BLCKSZ, 0);

	/*
	 * 我们使用关系扩展锁定来锁定其他试图同时扩展FSM的后端。它也锁定了主分支的扩展，这不必要，但扩展FSM的情况较少，因此似乎没有必要为此设置一个单独的锁定标签类型。
	 *
	 * 请注意，另一后端可能在我们获得锁时已经扩展或创建了关系。
	 */
	LockRelationForExtension(fc_rel, ExclusiveLock);

	/*
	 * 注意：如果 relcache 条目被关闭，重用此 smgr 指针可能会失败。只要我们在这里和最后一次使用指针之间只执行 smgr 级别的操作，这样做是安全的。
	 */
	fc_reln = RelationGetSmgr(fc_rel);

	/*
	 * 首先创建FSM文件，如果它不存在的话。如果smgr_cached_nblocks[FSM_FORKNUM]为正，则它必须存在，不需要进行smgrexists调用。
	 */
	if ((fc_reln->smgr_cached_nblocks[FSM_FORKNUM] == 0 ||
		 fc_reln->smgr_cached_nblocks[FSM_FORKNUM] == InvalidBlockNumber) &&
		!smgrexists(fc_reln, FSM_FORKNUM))
		smgrcreate(fc_reln, FSM_FORKNUM, false);

	/* 使缓存无效，以便 smgrnblocks() 请求内核。 */
	fc_reln->smgr_cached_nblocks[FSM_FORKNUM] = InvalidBlockNumber;
	fc_fsm_nblocks_now = smgrnblocks(fc_reln, FSM_FORKNUM);

	/* 根据需要进行扩展。 */
	while (fc_fsm_nblocks_now < fc_fsm_nblocks)
	{
		PageSetChecksumInplace((Page) fc_pg.data, fc_fsm_nblocks_now);

		smgrextend(fc_reln, FSM_FORKNUM, fc_fsm_nblocks_now,
				   fc_pg.data, false);
		fc_fsm_nblocks_now++;
	}

	UnlockRelationForExtension(fc_rel, ExclusiveLock);
}

/*
 * 在给定的FSM页面和槽位中设置值。
 *
 * 如果minValue > 0，则更新的页面还会搜索至少有minValue自由空间的页面。如果找到，返回其槽位编号，否则返回-1。
 */
static int fc_fsm_set_and_search(Relation fc_rel, FSMAddress fc_addr, uint16 fc_slot,
				   uint8 fc_newValue, uint8 fc_minValue)
{
	Buffer		fc_buf;
	Page		fc_page;
	int			fc_newslot = -1;

	fc_buf = fc_fsm_readbuf(fc_rel, fc_addr, true);
	LockBuffer(fc_buf, BUFFER_LOCK_EXCLUSIVE);

	fc_page = BufferGetPage(fc_buf);

	if (fsm_set_avail(fc_page, fc_slot, fc_newValue))
		MarkBufferDirtyHint(fc_buf, false);

	if (fc_minValue != 0)
	{
		/* 在我们还持有锁时搜索 */
		fc_newslot = fsm_search_avail(fc_buf, fc_minValue,
								   fc_addr.level == FSM_BOTTOM_LEVEL,
								   true);
	}

	UnlockReleaseBuffer(fc_buf);

	return fc_newslot;
}

/*
 * 在树中搜索具有至少min_cat自由空间的堆页面
 */
static BlockNumber fc_fsm_search(Relation fc_rel, uint8 fc_min_cat)
{
	int			fc_restarts = 0;
	FSMAddress	fc_addr = FSM_ROOT_ADDRESS;

	for (;;)
	{
		int			fc_slot;
		Buffer		fc_buf;
		uint8		fc_max_avail = 0;

		/* 读取FSM页面。 */
		fc_buf = fc_fsm_readbuf(fc_rel, fc_addr, false);

		/* 在页面内搜索 */
		if (BufferIsValid(fc_buf))
		{
			LockBuffer(fc_buf, BUFFER_LOCK_SHARE);
			fc_slot = fsm_search_avail(fc_buf, fc_min_cat,
									(fc_addr.level == FSM_BOTTOM_LEVEL),
									false);
			if (fc_slot == -1)
			{
				fc_max_avail = fsm_get_max_avail(BufferGetPage(fc_buf));
				UnlockReleaseBuffer(fc_buf);
			}
			else
			{
				/* 保持指针以供下面可能的更新 */
				LockBuffer(fc_buf, BUFFER_LOCK_UNLOCK);
			}
		}
		else
			fc_slot = -1;

		if (fc_slot != -1)
		{
			/*
			 * 降下树，或者如果我们已经在底部则返回找到的块。
			 */
			if (fc_addr.level == FSM_BOTTOM_LEVEL)
			{
				BlockNumber fc_blkno = fc_fsm_get_heap_blk(fc_addr, fc_slot);
				Page		fc_page;

				if (fc_fsm_does_block_exist(fc_rel, fc_blkno))
				{
					ReleaseBuffer(fc_buf);
					return fc_blkno;
				}

				/*
				 * 块超出了关系的结束。更新FSM，并从根节点重新开始。通常的“advancenext”行为对于这种罕见场景来说是最糟糕的，因为每个后面槽位都以相同的方式不可用。我们可以在同一个FSM页面上将所有受影响的槽位清零，但不期望该优化的好处能为其编译代码的体积辩护。
				 */
				fc_page = BufferGetPage(fc_buf);
				LockBuffer(fc_buf, BUFFER_LOCK_EXCLUSIVE);
				fsm_set_avail(fc_page, fc_slot, 0);
				MarkBufferDirtyHint(fc_buf, false);
				UnlockReleaseBuffer(fc_buf);
				if (fc_restarts++ > 10000) /* 与下面的理由相同 */
					return InvalidBlockNumber;
				fc_addr = FSM_ROOT_ADDRESS;
			}
			else
			{
				ReleaseBuffer(fc_buf);
			}
			fc_addr = fc_fsm_get_child(fc_addr, fc_slot);
		}
		else if (fc_addr.level == FSM_ROOT_LEVEL)
		{
			/*
			 * 在根节点，失败意味着FSM中没有具有足够自由空间的页面。放弃。
			 */
			return InvalidBlockNumber;
		}
		else
		{
			uint16		fc_parentslot;
			FSMAddress	fc_parent;

			/*
			 * 在更低级别，如果上层节点中的值未反映下层页面上的值，
			 * 可能会失败。更新上层节点，以避免再次陷入同样的陷阱，并
			 * 重新开始。
			 *
			 * 在这里存在竞争条件，如果另一个后端在我们释放页面后立即更新
			 * 该页面，并在我们之前获得父页面的锁。然后我们将用我们拥有的
			 * 过时信息更新父页面。这没关系，因为这种情况应当很少发生，
			 * 并会在下一个 vacuum 时被修复。
			 */
			fc_parent = fc_fsm_get_parent(fc_addr, &fc_parentslot);
			fc_fsm_set_and_search(fc_rel, fc_parent, fc_parentslot, fc_max_avail, 0);

			/*
			 * 如果上层页面严重过时，我们可能需要循环很多次，
			 * 一路更新它们。任何不一致最终应该得到纠正，循环应该结束。
			 * 然而，无限循环是可怕的，因此提供一个紧急阀门。
			 */
			if (fc_restarts++ > 10000)
				return InvalidBlockNumber;

			/* 从根节点重新开始搜索 */
			fc_addr = FSM_ROOT_ADDRESS;
		}
	}
}


/*
 * FreeSpaceMapVacuum 的递归核心
 *
 * 检查 addr 所指示的 FSM 页面，以及它的子页面，同时更新覆盖从
 * 开始到结束-1 的堆块范围的上层节点。
 * （如果结束超出地图的实际结束，这是可以的。）
 * 返回此页面上的最大空闲空间值。
 *
 * 如果 addr 超出 FSM 的结束位置，则将 *eof_p 设置为 true 并返回 0。
 *
 * 这以深度优先的顺序遍历树。 该树在物理上以深度优先的顺序存储，
 * 因此这应该相当高效的 I/O。
 */
static uint8 fc_fsm_vacuum_page(Relation fc_rel, FSMAddress fc_addr,
				BlockNumber fc_start, BlockNumber fc_end,
				bool *fc_eof_p)
{
	Buffer		fc_buf;
	Page		fc_page;
	uint8		fc_max_avail;

	/* 如果页面存在，则读取页面，否则返回 EOF */
	fc_buf = fc_fsm_readbuf(fc_rel, fc_addr, false);
	if (!BufferIsValid(fc_buf))
	{
		*fc_eof_p = true;
		return 0;
	}
	else
		*fc_eof_p = false;

	fc_page = BufferGetPage(fc_buf);

	/*
	 * 如果我们处于底层之上，则递归进入子节点，并修复
	 * 此级别存储的信息。
	 */
	if (fc_addr.level > FSM_BOTTOM_LEVEL)
	{
		FSMAddress	fc_fsm_start,
					fc_fsm_end;
		uint16		fc_fsm_start_slot,
					fc_fsm_end_slot;
		int			fc_slot,
					fc_start_slot,
					fc_end_slot;
		bool		fc_eof = false;

		/*
		 * 根据请求考虑的堆块范围，计算需要在此页面上更新的
		 * 插槽范围。第一个要更新的插槽是覆盖“开始”块的插槽，
		 * 最后一个插槽是覆盖“结束 - 1”的插槽。
		 * （这些工作将在每次递归调用中重复，但这足够廉价，无需担心。）
		 */
		fc_fsm_start = fc_fsm_get_location(fc_start, &fc_fsm_start_slot);
		fc_fsm_end = fc_fsm_get_location(fc_end - 1, &fc_fsm_end_slot);

		while (fc_fsm_start.level < fc_addr.level)
		{
			fc_fsm_start = fc_fsm_get_parent(fc_fsm_start, &fc_fsm_start_slot);
			fc_fsm_end = fc_fsm_get_parent(fc_fsm_end, &fc_fsm_end_slot);
		}
		Assert(fc_fsm_start.level == fc_addr.level);

		if (fc_fsm_start.logpageno == fc_addr.logpageno)
			fc_start_slot = fc_fsm_start_slot;
		else if (fc_fsm_start.logpageno > fc_addr.logpageno)
			fc_start_slot = SlotsPerFSMPage;	/* 不应该到这里... */
		else
			fc_start_slot = 0;

		if (fc_fsm_end.logpageno == fc_addr.logpageno)
			fc_end_slot = fc_fsm_end_slot;
		else if (fc_fsm_end.logpageno > fc_addr.logpageno)
			fc_end_slot = SlotsPerFSMPage - 1;
		else
			fc_end_slot = -1;		/* 不应该到这里... */

		for (fc_slot = fc_start_slot; fc_slot <= fc_end_slot; fc_slot++)
		{
			int			fc_child_avail;

			CHECK_FOR_INTERRUPTS();

			/* 在我们到达文件结尾后，只需清除其余插槽 */
			if (!fc_eof)
				fc_child_avail = fc_fsm_vacuum_page(fc_rel, fc_fsm_get_child(fc_addr, fc_slot),
											  fc_start, fc_end,
											  &fc_eof);
			else
				fc_child_avail = 0;

			/* 更新关于子项的信息 */
			if (fsm_get_avail(fc_page, fc_slot) != fc_child_avail)
			{
				LockBuffer(fc_buf, BUFFER_LOCK_EXCLUSIVE);
				fsm_set_avail(fc_page, fc_slot, fc_child_avail);
				MarkBufferDirtyHint(fc_buf, false);
				LockBuffer(fc_buf, BUFFER_LOCK_UNLOCK);
			}
		}
	}

	/* 现在获取页面上的最大值，以返回给调用者 */
	fc_max_avail = fsm_get_max_avail(fc_page);

	/* 
	 * 重置下一个槽指针。这鼓励使用低编号的
	 * 页面，增加后续清理可以截断
	 * 关系的机会。我们在这里不打算使用锁，也不标记页面
	 * 为脏页，如果它之前没有，因为这只是一个提示。
	 */
	((FSMPage) PageGetContents(fc_page))->fp_next_slot = 0;

	ReleaseBuffer(fc_buf);

	return fc_max_avail;
}


/* 
 * 检查块号是否超出了关系的末尾。这可以
 * 在WAL重放后发生，如果FSM已达到磁盘但它所指的
 * 新扩展页面未达到。
 */
static bool fc_fsm_does_block_exist(Relation fc_rel, BlockNumber fc_blknumber)
{
	SMgrRelation fc_smgr = RelationGetSmgr(fc_rel);

	/* 
	 * 如果低于缓存的nblocks，块肯定存在。否则，我们
	 * 面对一个权衡。我们选择与新鲜的nblocks进行比较，从而
	 * 产生lseek()的开销。替代方案是假设块不存在，
	 * 但这将导致FSM为刚刚记录的主分支扩展设置零可用空间
	 * 。
	 */
	return ((BlockNumberIsValid(fc_smgr->smgr_cached_nblocks[MAIN_FORKNUM]) &&
			 fc_blknumber < fc_smgr->smgr_cached_nblocks[MAIN_FORKNUM]) ||
			fc_blknumber < RelationGetNumberOfBlocks(fc_rel));
}
